Tańce gordyjskie Krzyśków

Limit pamięci: 32 MB

Na zakończenie tegorocznej edycji Pogromców Algorytmów Krzyśki odpowiedzialne za prawidłowy przebieg zawodowów (KC, KD, KO, KS) postanowili odtańczyć radosny taniec gordyjski. Taniec gordyjski to tradycyjny bajtocki taniec tańczony przez dwie pary tancerzy. Początkowo tancerze stoją w wierzchołkach kwadratu , w dwóch parach: i . Każda z par rozciąga między sobą sznurek. Tak więc na początku oba sznurki są rozciągnięte poziomo i równolegle do siebie.

Taniec składa się z ciągu ruchów, z których każdy może być ruchem następującego rodzaju:

• Tancerze stojący w punktach i zamieniają się miejscami (nie puszczając swoich sznurków) w ten sposób, że tancerz stojący w punkcie podnosi rękę ze sznurkiem do góry i idąc do punktu przepuszcza tancerza idącego z punktu do przed sobą, pod swoją ręką.
• Wszyscy tancerze wykonują obrót o 90 stopni w prawo nie puszczając sznurków, czyli tancerz, który stał w punkcie idzie do punktu , ten, który stał w punkcie idzie do punktu , ten, który stał w punkcie idzie do punktu , a ten, który stał w punkcie idzie do punktu .

W trakcie tańca sznurki plączą się ze sobą, jednak na koniec tańca powinny zostać rozplątane i znowu być rozciągnięte poziomo i równolegle do siebie. Tancerze nie muszą przy tym stać na tych samych miejscach, na których stali na początku. Taniec ten wymaga od tancerzy dużej wprawy, gdyż w trakcie tańca sznurki mogą być bardzo splątane i ciąg ruchów, który prowadziłby do ich rozplątania i rozciągnięcia poziomo i równolegle do siebie może być trudny do odgadnięcia.

Krzyśki to początkujący tancerze. Twoje zadanie polega na napisaniu programu, który pomógłby im zakończyć rozpoczęty taniec. Na podstawie ciągu już wykonanych ruchów Twój program powinien wyznaczyć minimalną liczbę ruchów pozwalających zakończyć taniec.

Przykład

Przykładowo, po wykonaniu ciągu ruchów otrzymujemy następującą konfigurację:

Najkrótszy ciąg ruchów, który pozwala zakończyć taniec ma długość 5 i jest nim .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis ciągu wykonanych ruchów w tańcu,
• wyznaczy minimalną liczbę ruchów potrzebnych do rozplątania sznurków i rozciągnięcia ich poziomo i równolegle do siebie (po wykonaniu tych ruchów tancerze nie muszą znajdować się na swoich początkowych pozycjach),
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna dodatnia liczba całkowita równa liczbie wykonanych ruchów, . W drugim wierszu zapisane jest jedno słowo długości złożone z liter i/lub . Kolejne litery tego słowa reprezentują kolejno wykonane ruchy w tańcu.

Wyjście

Twój program powinien wypisać na standardowe wyjście, w pierwszym i jedynym wierszu, jedną liczbę całkowitą - minimalną liczbę ruchów ( i/lub ) koniecznych do rozplątania sznurków i rozciągnięcia ich poziomo i równolegle do siebie.

Przykład

Dla danych wejściowych:

2
SS

poprawną odpowiedzią jest:

5

Autor zadania: Piotr Chrząstowski.